In a network of computers, such as the Internet, it is common for individual computer users to view images and documents which are not originally resident on their own computers. Such images and documents reside instead on other computer systems dedicated to the task of serving up the images and documents and delivering them to the computers of client users connected by a network. In such a network the computer that serves up images or documents is the server computer, and the computers into which users load media from the server computer are client computers.
Frequently, a user of a client computer in a network will browse many different documents and images interactively in a single computer-use session. Therefore, there is a need for systems that permit the most rapid possible interactive browsing of media over a network. Devising systems for rapid interactive browsing is complicated by the existence of at least three major components in every client-server interactive computer use session: (1) the client computer itself; (2) the network connecting the client computer to the server computer; (3) the server computer itself.
Interactive browsing of digital media can be made quicker and more responsive to the user by increasing the speed with which any of these three components operates, or by decreasing the quantity of data that the components need to process.
In the prior art for interactive server-client image-viewing systems, two significant innovations have been the storage of pyramided images on the server, and the partitioning of such images into uniform-sized tiles. Pyramided images facilitate zooming. Uniformly-tiled images facilitate quick access and delivery of image segments by the server computer.
A pyramided image is one in which the original digital image is supplemented by a succession of lower-resolution subsampled versions of the same image. Typically, each successive subsampled image has one-half the linear (row and column) resolution of its predecessor, and hence one-quarter the areal resolution of its predecessor. Typically, the chain of subsampled images continues down to a final one which is sufficiently small to be suitable for use as a thumbnail image on a computer screen. Pyramided images are particularly valuable in a server-client image-viewing system, because they mean that the client computer does not have to do any of the computational work required for image zooming; image zooming becomes, for the client computer, a matter not of computing a downsampled image but instead of requesting the appropriate downsampled image portion from the server computer and displaying it when received.
A uniformly-tiled image is one in which the image is decomposed into a uniform grid of uniformly sized, normally square, tiles. Common tile sizes are 64 rows by 64 columns, or other squares whose linear dimension is a power of two. Once an image has been decomposed into tiles, the tiles are saved in a file format such that a tile is identifiable by its offset in rows and columns (of tiles) from the image origin, which, by convention in digital imaging systems, is at the top left of the image. Storing an image in uniform-tile format greatly simplifies, facilitates, and speeds up the task of fetching an image portion, normally a rectangular window, from inside of an image. For example, in the action of panning, the user of the computer-viewing system causes a rectangular viewing window to traverse a larger, mostly unseen, image. Each time the viewing window pans to a new location, the computer system must find the requisite rectangular portion of the image from within the file and deliver it to the portion of the computer system that causes the image to be displayed. If the image is untiled, the task of finding a particular rectangular subportion of the image can be time-consuming; it can require stepping through all the pixels (picture elements) in the image up to the origin, and then to the opposite corner, of the rectangular subwindow. If, however images are uniformly tiled, the computer system software can readily identify the set of tiles minimally necessary to envelop any given subrectangle of the image, and, since the tiles are indexed by their row and column numbers, the system software can readily access them and deliver them to this display system.
An image can be both pyramided and uniformly tiled. In this case, each single resolution “layer” of the image, including the original full-resolution layer, is partitioned into image tiles of the same dimensions, for example, 64 rows by 64 columns. As the image pyramid progresses from one layer to a subsequent subsampled lower-resolution version of it, the overall size of a layer in pixels decrease by a factor of (approximately) four. (“Approximately” because of possible quantization roundoff.) But the sizes of the tiles into which the layer is partitioned stay constant. Hence the number of tiles per layer decreases by a factor of approximately four.
Uniformly-tiled images permit a computer seeking a rectangular subwindow of an image file to have random access to the minimal set of tiles required to envelop that subwindow. In order for the computer to gain random access to the tiles, it is critically important that the tiles fill a uniform regular grid over the image area rather than randomly or chaotically filling the image area. For example, the irregular area-filling tiling schemes of Roger Penrose (as described in U.S. Pat. No. 4,133,152) would not permit random access to rectangular image subportions.
Given a server computer with access to a set of pyramided, uniformly-tiled images, a uniform-tile client-server image-browsing system as practiced in the prior art, is one in which the same tiles as are resident on the server computer are transmitted over the network to client computers, where they are displayed and are perhaps also cached for later reuse.
If such a system has a caching feature, it may operate as follows. When the user of the client computer first displays an image, the client system requests from the server computer just those uniformly-shaped tiles necessary to render the newly requested portions of the image. The tiles so requested are placed in a cache, and the portions of them requisite for the current image display (cropped to the viewing window) are then displayed. The client computer's image tile cache is now seeded. Subsequently, when the user pans or zooms the image, thus causing a new portion of the image to be needed for display, the client computer (a) determines the minimal set of tiles needed to render the new image portion; (b) determines which, if any, of the requisite tiles are contained in the client computer's tile cache; (c) determines, as the residual (a)-(b) the set of tiles, if any, needed to be requested from the server; (d) requests the requisite tiles from the server; (e) on receipt of the requisite tiles from the server, adds them to the client-computer tile cache; (f) fetches from the client-computer tile cache the entire set of tiles required to render the new image portion, and causes them to the displayed, clipped to the current view window.
As image-viewing operations continue like this, data continues to be added into the client computer's tile cache. Consequently, the tile cache consumes progressively more of the client computer's memory. In order to limit the amount of memory used by the cache, procedures for systematic tile cache purging are incorporated into the client system. An upper bound for memory occupied by the cache is specified. When addition of new tiles to the client cache would cause this upper bound to be exceeded, tiles are purged from the cache. A least-recently-used tile-purging scheme is effective for determining which tiles to purge.
In the uniform-tile client-server image-viewing system described above, several of the specific operations described are facilitated by the fact that the cache maintained by the client is a regular grid of uniformly-sized tiles. In particular, the operations (a), (b), (e) and (f) described above are all made faster by the fact that the grid of tiles is uniform, so that a tile location can be immediately calculated from an image location, and tiles can be randomly accessed.
In interactive image browsing, the bottleneck to rapid image viewing in the three-part client-network-server system is almost always the network. In particular, in almost all client-network-server systems for image browsing, an analysis of the system capabilities for a typical individual client-server session will find that the speed of image browsing by an individual user on his or her client computer could not be increased by increasing the capabilities of the client or server computer unless the network were made to operate more efficiently.
In the uniform tile client server image viewing system described above, uniformly-sized tiles are used in all three components of the server-network-client system. Images are saved on the server in a uniform grid of tiles; each segment of image data transmitted over the network constitutes an identically-sized tile from the uniform grid, or a set of such tiles; the client computer's cache of image portions is a cache of a set of identically-sized tiles from the uniform grid, each of the same specification as the identically-sized tiles stored on the server computer and transmitted over the network.
However, the choice of the use of a grid of uniformly-sized tiles, though beneficial for image access efficiency on the server computer and client computers, is suboptimal for network efficiency.
The choice of a grid of uniformly-sized tiles forces the system to transmit a significant portion of unneeded pixels along with the needed pixels over the network. For example, suppose that all tiles are of size 64 rows by 64 columns. Whenever the image portion requested has height or width which is not an even multiple of 64 the height or width of the image portion actually delivered by the server computer to the client computer will have to be padded out to an even multiple of 64 in order that the image portion constitutes an exact set of tiles. Hence more pixel information than the client requires is transmitted over the network in such a system.
The choice of the grid of uniformly-sized tiles also forces the system to transmit more header information them would otherwise be the case. Each image tile will have a header specifying such things as where it lies in the image, its resolution, the unique ID of the image to which belongs, etc. Consequently, if the pixel transmission packet consists of several tiles rather than a single pixel-block, there will also be transmitted several tile headers instead of a single pixel-block header.
In summary, the choice of uniformly-sized tiles as the network transmission packet units is inefficient because of (a) padding: the transmission of extra pixels not actually needed for the client's current image display, and because of (b) excessive transmission of header information. Thus it is desirable to provide a system and method that increases the efficiency of the network part of the client-server image-viewing system by abandoning the insistence of prior-art systems on transmitting uniformly-sized tiles over the network.